package com.lsa.cormen.ch15.samples;

import java.util.Arrays;
import java.util.Collections;

public class Lcs {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arr1 = {2,3,5,9,11,12,15,16,19,20,22,27,28,40,41,51,52,53,65};
        int[] arr2 = {2,5,9,10,11,13,15,17,18,19,21,22,23,24,25,26,28,41,67,68,69,70, 65};
        Integer[] lcsTest = {2,5,9,11,15,19,22,28,41,65};
        
        int m = arr1.length;
        int n = arr2.length;
        
        int c[][] = new int[m+1][n+1]; // longest subsequence length
        int b[][] = new int[m+1][n+1]; // solution parent
        
        for (int i = 0; i < m; i++) {
            c[i][0] = 0;
        }
        for (int j = 0; j < n; j++) {
            c[0][j] = 0;
        }
        
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    c[i][j] = c[i-1][j-1] + 1;
                    b[i][j] = UPLEFT;
                }
                else if (c[i-1][j] >= c[i][j - 1]) {
                    c[i][j] = c[i-1][j];
                    b[i][j] = UP;
                }
                else {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = LEFT;
                }
            }
        }
        
        int i = m;
        int j = n;
        
        Integer lcs[] = new Integer[Math.min(m, n)];
        for (int k = 0; k < lcs.length; k++) {
            lcs[k] = -1;
        }
        int k = 0;
        
        while(i != 0 && j != 0) {
            if (b[i][j] == UPLEFT) { // same
                lcs[k++] = arr1[i-1]; 
                i--;
                j--;
            }
            else if (b[i][j] == UP) {
                i--;
            }
            else{
                j--;
            }
        }
        System.out.println(Arrays.asList(lcsTest));
        Collections.reverse(Arrays.asList(lcs).subList(0, k));
        System.out.println(Arrays.asList(lcs));
    }
    
    static int UP = 0;
    static int LEFT = 1;
    static int UPLEFT = 1;
}
